<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
    <!-- 
        解题思路：
        - 与归并排序中合并两个有序数组很相似
        - 将数组替换成链表就能解此题

        解题步骤：
        - 新建一个新链表，作为返回结果
        - 用指针遍历两个有序链表，并比较两个链表的当前节点，较小者先接入新链表，并将指针后移一步
        - 链表遍历结束，返回新链表

        时间复杂度：O(n) n为两个链表长度之和
        空间复杂度：O(1) 本题临时变量只有指针
     -->
</head>
<body>
    <script>
        var mergeTwoLists = function(list1, list2) {
            const res = new ListNode(0); // 创建新节点用于接收后面的节点
            let p = res;
            let p1 = list1;
            let p2 = list2;
            while(p1 && p2) { // 当p1指向链表和p2指向链表都还有节点时
                if (p1.val < p2.val) { // 如果p1的头节点值小，就接入res中，并使p1指向下一个节点
                    p.next = p1;
                    p1 = p1.next;
                } else { // 如果p2的头节点值小，就接入res中，并使p2指向下一个节点
                    p.next = p2;
                    p2 = p2.next;
                }
                p = p.next; // 同时使指向res链表的指针p后移
            }
            // 上面while循环结束时，可能还有某一个链表有节点没遍历完，即有个链表更长，此时可以直接把那个链表指针指向的节点接入res
            if (p1) { 
                p.next = p1;
            }
            if (p2) {
                p.next = p2;
            }
            return res.next;
        };
    </script>
</body>
</html>